package Leetcode_Second_Brush;

public class Solution005 {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 2) {
            return s;
        }
    
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
    
        int maxLength = 1; // 单个字符本身就是一个回文，所以初始长度为1
        int start = 0;
    
        // 单个字符的情况
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }
    
        // 两个字符的情况
        for (int i = 0; i < n - 1; i++) {
            if (s.charAt(i) == s.charAt(i + 1)) {
                dp[i][i + 1] = true;
                start = i;
                maxLength = 2;
            }
        }
    
        // 长度大于2的子串情况
        for (int length = 3; length <= n; length++) {
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) {
                    dp[i][j] = true;
                    start = i;
                    maxLength = length;
                }
            }
        }
    
        return s.substring(start, start + maxLength);
    }
    
}
